#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/*
Input:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
Output: 6
*/


//深度优先遍历
class Solution
{
public:
    int IsLandDFS(vector<vector<int>>& grid, int i ,int j) //i和j为我们所要访问的二维数组的下标
    {
        //判断是否在递归边界内
        if((i < grid.size() && (i >=0)) && (j < grid[0].size() && (j >= 0)))
        {   
            //若遍历到非陆地，则返回，这里也是递归边界 ？
            if(grid[i][j] == 0)
            {
                return 0;
            }
            else
            {
                //若遍历到陆地，则将该陆地处置为0，并向4个方向递归遍历，返回4个方向上的和作为结果
                grid[i][j] = 0;
                return 1+ IsLandDFS(grid,i-1,j)+IsLandDFS(grid,i+1,j)+IsLandDFS(grid,i,j-1)+IsLandDFS(grid,i,j+1);
            }
        }
        else
        {
            return 0;
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        int ans = 0;
        for(int i = 0; i < grid.size(); ++i)
        {
            for(int j = 0; j < grid[0].size(); ++j)
            {
                //遍历过程中，对于每一块区域，不断更新岛屿面积的最大值
                ans = max(ans,IsLandDFS(grid, i,j));
            }
        }
        return ans;
    }
};

int main()
{
    vector<int> a = {1,0,1,1,0,1,0,1};
    vector<int> b = {1,0,1,1,0,1,1,1};
    vector<int> c = {0,0,0,0,0,0,0,1};
    vector<vector<int>> grid;
    grid.push_back(a);
    grid.push_back(b);
    grid.push_back(c);

    Solution s;
    int ans = s.maxAreaOfIsland(grid);
    cout << ans << endl;

    return 0;
}